package brushexercises.day52;

/**
 * @Describe :53. 最大子数组和
 * @Author : sunzhenning
 * @Since : 2022/8/2 10:06
 * -2,1,-3,4,-1,2,1,-5,4
 */
public class NO_53_MaximumSubarray {

    public static void main(String[] args) {
        NO_53_MaximumSubarray maximumSubarray = new NO_53_MaximumSubarray();
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int ans = maximumSubarray.maxSubArray(nums);
        System.out.println(ans);
    }

    /**
     * 思路：1.求前置和s[]
     * 2.求前置和的最小值perMin[]
     * 3.要想得到最大子数组和，在[0,i-1]区间找一个j,使s[i] - s[j]最大。那么s[j]应该取最小值，即s[j] = preMin[j]
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int N = nums.length;
        int[] s = new int[N+1];
        int[] preMin = new int[N+1];
        for(int i=1;i<=N;i++){
            s[i] = s[i-1] + nums[i-1];
        }
        for(int i=1;i<=N;i++){
            preMin[i] = Math.min(preMin[i-1],s[i]);
        }
        int ans = Integer.MIN_VALUE;
        for(int i=1;i<=N;i++){
            ans = Math.max(ans,s[i]-preMin[i-1]);
        }
        return ans;
    }

}
